1. Field of the Invention
The present invention relates to a divider using restoring division for division using a dividend and divisor given by binary numbers, more particularly relates to a high radix divider for radix 2k division of a dividend to find a quotient for k number of bits at a time and a method for the same.
2. Description of the Related Art
Restoring division is known as a system of a subtractor (for example, see reference John L. Hennessy, David A. Paterson, translated by Mitsuaki Narita, Configuration and Design of Computer, 1st volume, pp. 191 to 199, Nikkei BP Co., April 1996).
Radix 2 restoring division obtains a quotient one bit at a time from the upper bit.
In this case, when a dividend is N bits, a minimum of N number of computations becomes required. For example, when the dividend is 32 bits, a minimum of 32 computations have to be performed.
When finding a quotient one bit at a time in this way, the number of computations becomes just too large, so there is the method of increasing the number of bits of the quotient found by one computation to 2 bits or more to decrease the number of computations. This is called high radix division.
When obtaining k number of bits at a time, the operation is called radix 2k division. For example, when performing radix 4 division of a 32-bit dividend, the quotient is found 2 bits at a time per computation and the minimum number of computations falls to 16. Similarly, with a radix 8, the number of computations becomes 11.
Below, radix 2 and radix 4 restoring division will be explained in detail.
Radix 2 Restoring Division
Here, the dividend is made A and the divisor is, made B. A and B are made N-bit signed binary numbers (two""s complements).
Note that the MSB appearing in the following explanation expresses to the most significant bit in the binary number and indicates the (Mxe2x88x921)th bit in the case of an M-digit binary number.
The registers include a sign register (one digit) for storing the sign of a quotient, a B register (N digits) for storing the divisor B, an R register (N digits) for storing the remainder, and a Q register (N digits) for storing the quotient.
All registers are initialized to zero.
The routine for division explained below is divided into the three first, second, and third stages STG1 to STG3.
The first stage STG1 is a preparatory stage, the third stage STG3 is a final stage for correction of the sign of the obtained quotient, and the second stage STG2 is the central stage of the division.
Each of the stages STG1, STG2, and STG3 end upon entry into the registers. The series of operations in a stage is performed in one cycle.
[Routine]
First Stage STG1
(1) The sign bit (MSB) of the dividend A and divisor B are referred to and the sign of the quotient is found in advance and stored in the sign register. Here, when negative, the sign=1.
(2) An absolute value of the dividend A is found and entered in the Q register.
(3) An absolute value of the divisor B is found and entered in the B register.
Second Stage STG2-1
(1) Rxe2x88x92B=diff(N digits) is calculated.
(2) When diff is not negative (MSB of diff is xe2x80x9c0xe2x80x9d), the divisor can be subtracted from the remainder.
At this time, the quotient judgement data Judge=1 and the new remainder is diff=Rxe2x88x92B=Re (N digits).
On the other hand, when diff is negative, the divisor cannot be subtracted from the remainder.
At this time, the quotient judgement data Judge=0 and the new remainder is R=Re (N digits).
(3) By combining the Re, Q, and Judge and shifting by one bit to the left, the value NEXT_R of the R register and the value NEXT_Q of the next Q register are found.
Namely,
NEXT_R={(Nxe2x88x922)th to 0th digits of Re, (Nxe2x88x921)th digit of Q}
NEXT_Q={(Nxe2x88x922)th to 0th digits of Q, Judge}
(4) The NEXT_R and NEXT_Q are respectively entered into the R, Q registers.
Second Stage STG2-2
The above operations of (1) to (4) are carried out in one cycle.
This is repeated for N number of times.
Third Stage STG3
(1) Rxe2x88x92B=diff (N digits) is calculated.
(2) When diff is not negative (MSB of diff is xe2x80x9c0xe2x80x9d), the divisor can be subtracted from the remainder.
At this time, the quotient judgement data is made Judge=1 and the new remainder is made diff=Rxe2x88x92B=Re (N digits).
On the other hand, when diff is negative, the divisor cannot be subtracted from the remainder.
At this time, the quotient judgement data is made Judge=0 and the new remainder is made R=Re (N digits).
(3) By combining Re and Q and shifting by one bit to the left, the value of the R register NEXT_R and value of the next Q register NEXT_Q are found.
Namely,
NEXT_R={(Nxe2x88x922)th to 0th digits of Re, (Nxe2x88x921)th digit of Q}
NEXT_Q={(Nxe2x88x922)th to 0th digits of Q, Judge}
The explanation up to here is the same as the second stage STG2.
(4) The sign of the quotient is corrected by referring to the sign register and the final quotient LAST_Q is found.
Namely,
Sign=1 (when negative):LAST_=xcx9cNEXT_Q+1 (two""s complement is taken).
Note that xe2x80x9cxcx9cxe2x80x9d indicates inversion.
Sign=0 (when not negative):LAST_Q=NEXT_Q
On the other hand. the final remainder is Re.
(5) The LAST_Q is entered into the Q register and Re is entered into the R register.
Here, the Q register shows the quotient and the remainder shows the R register.
The above completes the division by radix 2 restoring division.
FIG. 1 is a circuit diagram of an example of the general configuration of a restoring division subtractor.
The restoring division subtractor comprises, as shown in FIG. 1, an exclusive OR gate 110 for obtaining the sign of the quotient in the first stage STG1, absolute value generators 111 and 112 for obtaining absolute values of the dividend A and the divisor B in the first stage STG1, a quotient/remainder Judgement unit 113 for the processing of the second stage STG2, a sign inversion unit 114 for the processing of the third stage STG3, a selector 115, stage selecting selectors 116 to 119 operated by a control signal CTL, a sign register 120, a B register 121, an R register 122, and a Q register 123.
The quotient/remainder judgement unit 113 is for realizing the second stage STG2-1 in the above explained routine. An example of the configuration is shown in FIG. 2.
As shown in FIG. 2, the quotient/remainder judgement unit 113 is comprised by a subtractor 131 for subtraction of (Rxe2x88x92B) in the processing of the above second stage STG2-1(1), a selector 132 for obtaining a new remainder Re based on the quotient judgement in the processing of the second stage2-1(2), and bit matchers 133 and 134 for the processing of the second stage STG2-1(3).
In a restoring division subtractor configured in this way, by properly giving a control signal CTL, the operations of the above first stage STG1, second stage STG2, and third stage STG3 are switched.
FIG. 3 is a view of the process of the operation of the subtractor.
In this example, 77654321h/00000007h was calculated.
When looking at the column xe2x80x9cJudgexe2x80x9d in FIG. 3, the process by which the quotient is found bit by bit from the upper bit can be understood.
Radix 4 Restoring Division
The case of a radix 4 differs from the case of a radix 2 in the point that the quotient is obtained 2 bits at a time. Also, only the part of the second stage STG2-1 differs in the routine of the above restoring division.
[Routine]
Second Stage 2-1
(1) 2B(N+1 digits) is found by bit shifting. 3B(N+2 digits) is found from 2B+B.
Then,
Rxe2x88x923B=diff3(N+2 digits)
Rxe2x88x922B=diff2(N+1 digits)
Rxe2x88x92Bdiff1(N digits)
are calculated in parallel.
(2) If diff3 is not negative ((N+1)th bit is xe2x80x9c0xe2x80x9d), the new remainder is made diff3=Rxe2x88x923B=Re (N digits, upper 2 bits truncated) and the quotient judgement is made Judge=11 (2 digits).
If diff3 is negative and diff2 is not negative (Nth bit is xe2x80x9c0xe2x80x9d), the new remainder is made diff2=Rxe2x88x922B=Re (N digits, upper 1 bit truncated) and the quotient judgement is made Judge=10 (2 digits).
If diff3 is negative, diff2 is negative, and diff1 is not negative ((Nxe2x88x921)th bit is xe2x80x9c0xe2x80x9d), the new remainder is made diff1=Rxe2x88x92B=Re (N digits) and the quotient judgement is made Judge=01 (2 digits).
If diff3, diff2, and diff1 are all negative, the new remainder is made R=Re (N digits) and the quotient judgement is made Judge=00 (2 digits).
(3) By combining Re and Q and shifting the result two bits to the left, the value of the next R register NEXT_R and the value of the next Q register NEXT_Q are found.
Namely,
NEXT_R={(Nxe2x88x923)th to 0th digits of Re, (Nxe2x88x921)th to (Nxe2x88x922)th digits of Q}
NEXT_Q={(Nxe2x88x923)th to 0th digits of Q, Judge}
(4) Next_R and NEXT_Q are respectively entered into the R and Q registers.
FIG. 4 is a circuit diagram of the conventional configuration of a radix 4 quotient/remainder judgement unit based on the routine (second stage 2-1).
The quotient/remainder judgement unit 113a is comprised by, as shown in FIG. 4, a shifter 141 for obtaining 2B, an adder 142 for obtaining 3B, and subtractors 143 to 145 for obtaining diff1, diff2, and diff3 in the processing of the second stage 2-1(1), selectors 146 to 148 for obtaining a new remainder Re based on a sign bit of the subtraction result in the processing of the second stage STG2-1 (2), selectors 149 to 151 for obtaining quotient judgements, and bit matchers 152 and 153 for the processing of the second stage STG2-1(3).
FIG. 5 is a view of the process of the operation of the divider.
In this example as well, 77654321h/00000007h was calculated in the same way as in the above case of a radix 2.
As clear from FIG. 5, since the quotient is found 2 bits at a time in the second stage STG2, the number of computations required in the second stage STG2 is 16. It was 32 times in the case of a radix 2.
In this way, the number of computations can be reduced by using a high radix.
The above explained radix 2 quotient/remainder judgement unit 113 in FIG. 2 requires one N-bit width subtractor 131 and one N-bit width 2:1 selector 132.
On the other hand, the radix 4 quotient/remainder judgement unit 113 in FIG. 4 requires one (N+1) bit width adder 142 for 2B+B, one N-bit width subtractor 145 for (Rxe2x88x92B), one (N+1) bit width subtractor 144 for Rxe2x88x922B, three N-bit width 2:1 selectors, and three two-bit width 2:1 selectors 149 to 151.
In this way, in a high radix subtractor, there is the disadvantage that the number of processors required increases remarkably and the circuit becomes large in size.
An object of the present invention is to provide a high radix divider capable of reducing the size of the circuit of the quotient/remainder judgement unit of a high radix restoring division divider and a method for the same.
According to a first aspect of the present invention, there is provided a high radix divider for radix 2k division of a dividend A by a divisor B to find a quotient for k number of bits at a time, comprising a multiple generating means for shifting bits of the divisor B to generate 2sxc3x97B (s is a non-negative integer including xe2x80x9c0xe2x80x9d and sxe2x89xa6k); a first comparator for receiving as input the divisor B and a remainder R, judging whether the divisor B is equal to or smaller than the remainder R, and outputting the judgement result; at least one second comparator for receiving as input the 2sxc3x97B generated by the multiple generating means and the remainder R, judging whether 2sxc3x97B is equal to or smaller than the remainder R, and outputting the judgement result; at least one three-input comparator having a 3:2 compressor stage for receiving as input 2sxc3x97B, +/xe2x88x922t(t less than s)xc3x97B, and a remainder R as three m-bit width binary numbers, converting the total to two m-bit width binary numbers (co, S), and outputting the same, and a non-negative judgement stage for judging whether the total value is non-negative based on the two binary numbers (Co, S) output from the above 3:2 compressor stage; a selection circuit for obtaining a first output y selecting one of 2sxc3x97B and xe2x80x9c0xe2x80x9d and a second output z selecting one of the divisor B and xe2x80x9c0xe2x80x9d in accordance with a comparison result of the three-input comparator, second comparator, and first comparator; a three-input adder/subtractor for receiving as input the remainder R and first output and second output of the selection circuit as three m-bit width binary numbers and performing complex addition and subtraction of {Rxe2x88x92(y+z)} in parallel by a single ripple carry to find a new remainder Re; and a matcher for performing bit matching in accordance with a comparison result of the three-input comparator, second comparator, and first comparator to determine a quotient Q.
Further, in the present invention, the 3:2 compressor stage of said three-input comparator comprises an m-bit width 3:2 compressor for receiving as input two binary numbers 2sxc3x97B and +/xe2x88x922t(t less than s)xc3x97B as they are for each bit and for receiving as input one binary number R by taking a negation of each bit.
Further, in the present invention, a non-negative judgement stage of the three-input comparator comprises an m-digit adder having 0 to mxe2x88x921 number of inputs A and inputs B forming m number of pairs and a carry-in input Cin, has the 0th digit S-output of the 3:2 compressor stage as the input of the carry-in input Cin, has the corresponding 0th to (mxe2x88x921)th digit Co outputs as the B0 to Bmxe2x88x921 inputs, has the i(i less than m)th digit S-output as the (ixe2x88x921) A-input, and has the (mxe2x88x921) digit S-output as the Amxe2x88x921 input and the three-input comparator judges and outputs the (mxe2x88x921)th digit SUMmxe2x88x921 of an addition output of the adder.
Further, in the present invention, the m-digit adder comprises only by logic gates relating to generation of an (mxe2x88x921)th digit SUMmxe2x88x921 of the addition output.
Further, in the present invention, the three-input adder/subtractor comprises a 3:2 compressor stage for converting a total of three m-bit width binary numbers to two m-bit width binary numbers (Co, S) for output and an m-digit adder for finding the sum of the digits based on the two binary numbers (Co, S) output from the 3:2 compressor stage.
Further, in the present invention, the 3:2 compressor stage of the three-input adder/subtractor comprises an m-bit width 3:2 compressor receiving as input one binary number R as it is for each bit and receiving as input two binary numbers y and z by taking a negation of each bit.
Further, in the present invention, an m-digit adder of the three-input adder/subtractor has 0 to mxe2x88x921 number of inputs A and inputs B forming m number of pairs and a carry-in input Cin, has a logic xe2x80x9c1xe2x80x9d as the input of a carry-in input Cin, has the corresponding 0th digit to (mxe2x88x921) digit Co outputs as the B0 to Bmxe2x88x921 inputs, has the i(i less than m)th digit S outputs as the (ixe2x88x921) number of A inputs, and has the (mxe2x88x921)-digit S outputs as the Amxe2x88x921 number of inputs and the three-input adder/subtractor uses the SUM0 to SUMmxe2x88x921 of the addition outputs of the m-digit adder and the 0th digit S output of the 3:2 compressor as the output of the result of addition/subtraction.
Further, in the present invention, the selection circuit comprises a first selector for selecting one of different k-bit first and second judgement data in accordance with a judgement result of the first comparator; a second selector for selecting one of a further different k-bit third judgement data and the first or second judgement data selected by the first selector in accordance with a judgement result of the second comparator; a third selector for selecting one of a further different fourth judgement data and the first, second, or third judgement data selected by the second selector in accordance with a judgement result of the three-input comparator and outputting the selected data to the matcher as quotient judgement data; a fourth selector for selecting one of 2sxc3x97B or xe2x80x9c0xe2x80x9d based on an upper bit of the quotient judgement data to select the first output y; and a fifth selector for selecting one of B or xe2x80x9c0xe2x80x9d based on a lower bit of the quotient judgement data to select the second output z.
Further, in the present invention, the selection circuit selects the fourth judgement data as quotient Judgement data regardless of a Judgement result of the second and first comparators when obtaining a judgement result that (B+2B) is equal to or smaller than a remainder R in the three-input comparator, selects the third judgement data as quotient judgement data regardless of a judgement result of the first comparator when obtaining a judgement result that (B+2B) is larger than a remainder R in the three-input comparator and obtaining a judgement result that (2sxc3x97B) is equal to or smaller than a remainder R in the second comparator, and selects the first or second judgement data as quotient judgement data when obtaining a judgement result that 2sxc3x97B is larger than a remainder R in the second comparator.
According to a second aspect of the present invention, there is provided high radix divider for radix 4 division of a dividend A by a divisor B to find a quotient for 2 number of bits at a time, comprising a multiple generating means for shifting the bits of the divisor B to generate 2B; a first comparator for receiving as input the divisor B and a remainder R, judging whether the divisor B is equal to or smaller than the remainder R, and outputting the judgement result; a second comparator for receiving as input the 2B generated by the multiple generating means and the remainder R, judging whether 2B is equal to or smaller than the remainder R, and outputting the judgement result; a three-input comparator comprising a 3:2 compressor stage for receiving as input the 2B, B, and a remainder R as three m-bit width binary numbers, converting the total to two m-bit width binary numbers (Co, S), and outputting the same and a non-negative judgement stage for judging whether or not the total value is non-negative based on the two binary numbers (Co, S) output from the 3:2 compressor stage; a selection circuit for obtaining a first output y selecting one of 2B and xe2x80x9c0xe2x80x9d and a second output z selecting one of the divisor B and xe2x80x9c0xe2x80x9d in accordance with a comparison result of the three-input comparator, second comparator, and a third comparator; a three-input adder/subtractor for receiving as input a remainder R and the first output y and second output z of the selection circuit as three m-bit width binary numbers and performing complex addition and subtraction of {Rxe2x88x92(y+z)} in parallel by a single ripple carry to find a new remainder Re; and a matcher for performing bit matching to determine a quotient Q in accordance with a comparison result of the three-input comparator, second comparator, and first comparator.
According to a third aspect of the present invention, there is provided a high radix division method for radix 2k division of a dividend A by a divisor B to find a quotient by k number of bits at a time, including a step of shifting the bits of the divisor B to generate 2s (s is a non-negative integer including xe2x80x9c0xe2x80x9d and sxe2x89xa6k)xc3x97B; a first comparison step of comparing the divisor B and a remainder R to judge whether the divisor B is equal to or smaller than the remainder R; a second comparison step of comparing 2sxc3x97B and the remainder R to judge whether 2sxc3x97B is equal to or smaller than the remainder R; a third comparison step of converting a total of 2sxc3x97B, +/xe2x88x922t(t less than s)xc3x97B, and the remainder R as three m-bit width binary numbers to two m-bit width binary numbers (Co, S) and judging whether the total value is non-negative based on the two binary numbers (Co, S); a step of obtaining a y selecting one of 2sxc3x97B or xe2x80x9c0xe2x80x9d and z selecting one of B or xe2x80x9c0xe2x80x9d in accordance with a comparison result of the third, second, and first comparison steps; a step of performing complex addition and subtraction of {Rxe2x88x92(y+z)} in parallel by a single ripple carry to find a new remainder Re; and a step of performing bit matching to determine a quotient Q in accordance with a comparison result of the third, second, and first comparison steps; wherein the first comparison step, second comparison step, and third comparison step are performed in parallel.
According to the present invention, 2sxc3x97B (s is a non-negative integer including xe2x80x9c0xe2x80x9d and sxe2x89xa6k) is generated by shifting the bits of the divisor B in the multiple generating means and supplied to the second comparator and the three-input comparator.
Then, the following comparison operations are performed in parallel in the first comparator, second comparator, and three-input comparator.
In the first comparator, a divisor B and a remainder R are input, whether the divisor B is equal to or smaller than the remainder R is judged, and the judgement result is output to a selection circuit.
In the second comparator, the 2sxc3x97B generated in the multiple generating means and the remainder R are input, whether 2sxc3x97B is equal to or smaller than the remainder R is judged, and the judgement result is output to the selection circuit.
In the three-input comparator, the three m-bit width binary numbers 2sxc3x97B, +/xe2x88x922t(t less than s)B, and remainder R are input, the total of the same is converted to two m-bit width binary numbers (Co, S) in the 3:2 compressor stage, whether the total value is non-negative based on the two binary numbers (Co, S) output from the 3:2 compressor is judged in the non-negative judgement stage, and the judgement result is output to the selection circuit.
In accordance with the comparison results of the three-input comparator, second comparator, and first comparator, in the selection circuit, one of 2sxc3x97B or xe2x80x9c0xe2x80x9d is selected to obtain a first output y while one of B or xe2x80x9c0xe2x80x9d is selected to obtain a second output z and the same is supplied to the three-input adder/subtractor.
In the three-input adder/subtractor, the complex addition and subtraction {Rxe2x88x92(y+z)} are performed in parallel by a single ripple carry and the new remainder Re is found.
Then, in accordance with the comparison results of the three-input comparator, second comparator, and first comparator, the bit matching is performed and the quotient Q is determined in the matcher.
Also, in the so-called multiple comparison method in the three-input comparator, it is possible to use methods as in the following examples based on for example numbers of multiples of +/xe2x88x922s such as +/xe2x88x92B, +/xe2x88x922B, +/xe2x88x924B, +/xe2x88x928B, and +/xe2x88x9216B generated by the multiple generating means.
3B=(B+2B)xe2x89xa6R
5B=(B+4B)xe2x89xa6R
6B=(2B+4B)xe2x89xa6R
7B=(xe2x88x92B+8B)xe2x89xa6R
9B=(B+8B)xe2x89xa6R
10B=(2B+8B)xe2x89xa6R
12B=(4B+8B)xe2x89xa6R
14B=(xe2x88x924B+16B)xe2x89xa6R
15B=(xe2x88x921B+16B)xe2x89xa6R
17B=(B+16B)xe2x89xa6R
18B=(2B+16B)xe2x89xa6R
20B=(4B+16B)xe2x89xa6R
24B=(8B+16B)xe2x89xa6R